package madixin.t230;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

class Solution {

    int res = -1;
    int count = 0;

    /**
     * 递归
     */
    public int kthSmallest(TreeNode root, int k) {
        midOrder(root, k);  
        return res;
    }

    private void midOrder(TreeNode node, int k) {
        if (node == null) {
            return;
        }
        midOrder(node.left, k);
        count++;
        if (count == k) {
            res = node.val;
            return;
        }
        midOrder(node.right, k);
    }


    /**
     * 迭代
     */
    public int kthSmallest1(TreeNode root, int k) {
        if (root == null) {
            return -1;
        }
        int count = 0;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            count++;
            if (count == k) {
                return node.val;
            }
            cur = node.right;
        }
        return -1;
    }
}